class IP

Definition (IPS)

Consider the following

An interactive proof system (IPS) is a protocol between $P$ and $V$ where

$P$ and $V$ are given an input $x$
through exchange of messages $P$ tries to prove to $V$ that $x \in L$ (i.e. that $x$ is in language $L$ )
at end of interaction $V$ outputs "accept" if proof is satisfactory or "reject" if not

(or say that language $L$ is in $\mathbf{LP}[k]$ , if the following hold, for $V$ having $k$ -round interaction with $P$ ,)

Require that

(completeness) if both $P$ and $V$ follow the protocol and $x \in L$ , then $\Pr[V \text{ accepts } x] \geq \frac{2}{3}$ i.e., $x \in L \Rightarrow \exists P \Pr[\mathtt{out}_V \langle V,P \rangle (x) = 1] \geq 2/3$
(soundness) if $x \notin L$ and $V$ follows the protocol, then regardless of what $P$ does, $\Pr[V \text{ rejects } x] \geq \frac{2}{3}$ i.e., $x \notin L \Rightarrow \forall P \Pr[\mathtt{out}_V \langle V,P \rangle (x) = 1] \leq 2/3$

(probabilities over choice of $m$ -bit random variable $r \in_R \{0,1\}^m$ for interaction $\langle f,g \rangle (x)$ over $r$ )

Define $\mathbf{IP} = \cup_{c\geq 1} \mathbf{IP}[n^c]$ .

In other words, the class $\mathbf{IP}$ is the class of languages $L$ such that there exists an IPS for $L$ .

NP can be thought of an IPS where $P$ sends $V$ exactly one message, hence $\mathbf{NP} \subset \mathbf{IP}$
zero-knowledge proofs (ZKP) are IP proofs with the additional requirement of zero-knowledge where VV does not learn anything other than the fact that the statement is true; it is known that 𝐙𝐊𝐏⊂𝐈𝐏\mathbf{ZKP} \subset \mathbf{IP}
- $\mathbf{ZKP} \subseteq \mathbf{NP}$ in fact
every language in P♯P has an IPS [Lund et al 1992]
compare to dIP, where the verifier is deterministic
MIP, multi-prover interactive proof, a special case